#
# @lc app=leetcode.cn id=332 lang=python
#
# [332] 重新安排行程
#

# @lc code=start
from collections import defaultdict
class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        self.tickets = tickets
        self.dict = defaultdict(list)
        for from_to in self.tickets:
            self.dict[from_to[0]].append(from_to[1])
        for value in self.dict.values():
            value.sort(reverse=True)
        self.result = []
        self.loop('JFK')
        return self.result[::-1]

    def loop(self, key):
        while self.dict[key]:
            airport = self.dict[key].pop()
            self.loop(airport)
        self.result.append(key)

        
# @lc code=end

